package com.klun.project.common.constans.leetcode;
//给定一个二叉搜索树的根节点 root ，和一个整数 k ，
// 请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
// 示例 1：
//输入：root = [3,1,4,null,2], k = 1
//输出：1
// 示例 2：
//输入：root = [5,3,6,2,4,null,null,1], k = 3
//输出：3
// 提示：
// 树中的节点数为 n 。
// 1 <= k <= n <= 104
// 0 <= Node.val <= 104
// 进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树

import com.klun.project.common.constans.entity.TreeNode;
import com.klun.project.common.constans.utils.ParseUtils;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Solution230 {

	public int kthSmallest1(TreeNode root, int k) {
		MyBst bst = new MyBst(root);
		return bst.kthSmallest(k);
	}
	class MyBst {
		TreeNode root;
		Map<TreeNode, Integer> nodeNum;

		public MyBst(TreeNode root) {
			this.root = root;
			this.nodeNum = new HashMap<TreeNode, Integer>();
			countNodeNum(root);
		}

		// 返回二叉搜索树中第k小的元素
		public int kthSmallest(int k) {
			TreeNode node = root;
			while (node != null) {
				int left = getNodeNum(node.left);
				if (left < k - 1) {
					node = node.right;
					k -= left + 1;
				} else if (left == k - 1) {
					break;
				} else {
					node = node.left;
				}
			}
			return node.val;
		}

		// 统计以node为根结点的子树的结点数
		private int countNodeNum(TreeNode node) {
			if (node == null) {
				return 0;
			}
			nodeNum.put(node, 1 + countNodeNum(node.left) + countNodeNum(node.right));
			return nodeNum.get(node);
		}

		// 获取以node为根结点的子树的结点数
		private int getNodeNum(TreeNode node) {
			return nodeNum.getOrDefault(node, 0);
		}
	}

	public int kthSmallest(TreeNode root, int k) {
		Deque<TreeNode> stack = new ArrayDeque<>();
		while (root != null || !stack.isEmpty()) {
			while (root != null) {
				stack.push(root);
				root = root.left;
			}
			root = stack.pop();
			--k;
			if (k == 0) {
				break;
			}
			root = root.right;
		}
		return root.val;
	}


	public static void main(String[] args) {
		Solution230 solution = new Solution230();
//		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
		TreeNode treeNode = ParseUtils.ArrayToBTree("[3,1,4,null,2]");
		System.out.println(solution.kthSmallest(treeNode, 1));
	}
}
